home *** CD-ROM | disk | FTP | other *** search
/ Almathera Ten Pack 3: CDPD 3 / Almathera Ten on Ten - Disc 3: CDPD3.iso / fish / 001-100 / 001-025 / 004 / bison / output.c < prev    next >
C/C++ Source or Header  |  1995-03-17  |  22KB  |  1,205 lines
  1. /* Output the generated parsing program for bison,
  2.    copyright (C) 1984 Bob Corbett and Richard Stallman
  3.  
  4.    Permission is granted to anyone to make or distribute verbatim copies of this program
  5.    provided that the copyright notice and this permission notice are preserved;
  6.    and provided that the recipient is not asked to waive or limit his right to
  7.    redistribute copies as permitted by this permission notice;
  8.    and provided that anyone possessing an executable copy
  9.    is granted access to copy the source code, in machine-readable form,
  10.    in some reasonable manner.
  11.  
  12.    Permission is granted to distribute derived works or enhanced versions of
  13.    this program under the above conditions with the additional condition
  14.    that the entire derivative or enhanced work
  15.    must be covered by a permission notice identical to this one.
  16.  
  17.    Anything distributed as part of a package containing portions derived
  18.    from this program, which cannot in current practice perform its function usefully
  19.    in the absense of what was derived directly from this program,
  20.    is to be considered as forming, together with the latter,
  21.    a single work derived from this program,
  22.    which must be entirely covered by a permission notice identical to this one
  23.    in order for distribution of the package to be permitted.
  24.  
  25.  In other words, you are welcome to use, share and improve this program.
  26.  You are forbidden to forbid anyone else to use, share and improve
  27.  what you give them.   Help stamp out software-hoarding!  */
  28.  
  29. /* functions to output parsing data to various files.  Entries are:
  30.  
  31.   output_headers ()
  32.  
  33. Output constant strings to the beginning of certain files.
  34.  
  35.   output_trailers()
  36.  
  37. Output constant strings to the ends of certain files.
  38.  
  39.   output ()
  40.  
  41. Output the parsing tables and the parser code to ftable.
  42.  
  43. The parser tables consist of:  (starred ones needed only for the semantic parser)
  44.  
  45. yytranslate = vector mapping yylex's token numbers into bison's token numbers.
  46.  
  47. * yyrhs = vector of items of all rules.
  48.         This is exactly what ritems contains.
  49.  
  50. * yyprhs[r] = index in yyrhs of first item for rule r.
  51.  
  52. yyr1[r] = symbol number of symbol that rule r derives.
  53.  
  54. yyr2[r] = number of symbols composing right hand side of rule r.
  55.  
  56. * yystos[s] = the symbol number of the symbol that leads to state s.
  57.  
  58. yydefact[s] = default rule to reduce with in state s,
  59.           when yytable doesn't specify something else to do.
  60.           Zero means the default is an error.
  61.  
  62. yydefgoto[i] = default state to go to after a reduction of a rule that
  63.            generates variable ntokens + i, except when yytable
  64.            specifies something else to do.
  65.  
  66. yypact[s] = index in yytable of the portion describing state s.
  67.             The lookahed token's type is used to index that portion
  68.             to find out what to do.
  69.  
  70.         If the value in yytable is positive,
  71.         we shift the token and go to that state.
  72.  
  73.         If the value is negative, it is minus a rule number to reduce by.
  74.  
  75.         If the value is zero, the default action from yydefact[s] is used.
  76.  
  77. yypgoto[i] = the index in yytable of the portion describing 
  78.              what to do after reducing a rule that derives variable i + ntokens.
  79.              This portion is indexed by the parser state number
  80.          as of before the text for this nonterminal was read.
  81.          The value from yytable is the state to go to.
  82.  
  83. yytable = a vector filled with portions for different uses,
  84.           found via yypact and yypgoto.
  85.  
  86. yycheck = a vector indexed in parallel with yytable.
  87.       It indicates, in a roundabout way, the bounds of the
  88.       portion you are trying to examine.
  89.  
  90.       Suppose that the portion of yytable starts at index p
  91.       and the index to be examined within the portion is i.
  92.       Then if yycheck[p+i] != i, i is outside the bounds
  93.       of what is actually allocated, and the default
  94.       (from yydefact or yydefgoto) should be used.
  95.       Otherwise, yytable[p+i] should be used.
  96.  
  97. YYFINAL = the state number of the termination state.
  98. YYFLAG = most negative short int.  Used to flag ??
  99. YYNTBASE = ntokens.
  100.  
  101. */
  102.  
  103. #include <stdio.h>
  104. #include "machine.h"
  105. #include "new.h"
  106. #include "files.h"
  107. #include "gram.h"
  108. #include "state.h"
  109.  
  110. #define    MAXTABLE 32767
  111.  
  112.  
  113. extern int tokensetsize;
  114. extern int final_state;
  115. extern core **state_table;
  116. extern shifts **shift_table;
  117. extern reductions **reduction_table;
  118. extern short *accessing_symbol;
  119. extern unsigned *LA;
  120. extern short *LAruleno;
  121. extern short *lookaheads;
  122. extern char *consistent;
  123. extern short *goto_map;
  124. extern short *from_state;
  125. extern short *to_state;
  126.  
  127.  
  128. static int nvectors;
  129. static int nentries;
  130. static short **froms;
  131. static short **tos;
  132. static short *tally;
  133. static short *width;
  134. static short *actrow;
  135. static short *state_count;
  136. static short *order;
  137. static short *base;
  138. static short *pos;
  139. static short *table;
  140. static short *check;
  141. static int lowzero;
  142. static int high;
  143.  
  144.  
  145.  
  146. static char *guardstr[] = {
  147.     "extern int yyerror;\n",
  148.     "extern int yycost;\n",
  149.     "extern char * yymsg;\n",
  150.     "extern YYSTYPE yyval;\n\n",
  151.     "yyguard(n, yyvsp, yylsp)\n",
  152.     "register int n;\n",
  153.     "register YYSTYPE *yyvsp;\n",
  154.     "register YYLTYPE *yylsp;\n",
  155.     "{\n",
  156.     "yyerror = 0;\n",
  157.     "yycost = 0;\n",
  158.     "yymsg = 0;\n",
  159.     "switch (n)\n",
  160.     "{",
  161.     NULL
  162. };
  163.  
  164. static char *actstr[] = {
  165.     "extern YYSTYPE yyval;\n",
  166.     "extern int yychar;\n",
  167.     "yyaction(n, yyvsp, yylsp)\n",
  168.     "register int n;\n",
  169.     "register YYSTYPE *yyvsp;\n",
  170.     "register YYLTYPE *yylsp;\n",
  171.     "{\n",
  172.     "switch (n)\n",
  173.     "{",
  174.     NULL
  175. };
  176.  
  177. #define    ACTSTR_SIMPLE    "\n  switch (yyn) {\n"
  178.  
  179. output_headers()
  180. {
  181.   if (semantic_parser) {
  182.     fprintf(fguard, "\n#include \"%s\"\n", attrsfile);
  183.     emit(guardstr);
  184.     fprintf(faction, "\n#include \"%s\"\n", attrsfile);
  185.     emit(actstr);
  186.   } else {
  187.     fprintf(faction, ACTSTR_SIMPLE);
  188.   }
  189.   if (semantic_parser)
  190.     fprintf(ftable, "#include \"%s\"\n", attrsfile);
  191.   fprintf(ftable, "#include <stdio.h>\n\n");
  192. }
  193.  
  194.  
  195.  
  196. output_trailers()
  197. {
  198.   if (semantic_parser)
  199.     {
  200.       fprintf(fguard, "\n    }\n}\n");
  201.       fprintf(faction, "\n    }\n}\n");
  202.     }
  203.   else
  204.     fprintf(faction, "\n}\n");
  205. }
  206.  
  207.  
  208.  
  209. output()
  210. {
  211.   free_itemsets();
  212.   output_defines();
  213.   output_token_translations();
  214.   if (semantic_parser)
  215.     output_gram();
  216.   FREE(ritem);
  217.   if (semantic_parser)
  218.     output_stos();
  219.   output_rule_data();
  220.   output_actions();
  221.   output_parser();
  222.   output_program();
  223. }
  224.  
  225.  
  226.  
  227. output_token_translations()
  228. {
  229.   register int i, j;
  230.   register short *sp;
  231.  
  232.   if (translations)
  233.     {
  234.       fprintf(ftable, "\n#define YYTRANSLATE(x) (yytranslate[x])\n");
  235.     
  236.       if (ntokens < 127)  /* play it very safe; check maximum element value.  */
  237.         fprintf(ftable, "\nstatic char yytranslate[] = {     0");
  238.       else
  239.     fprintf(ftable, "\nstatic short yytranslate[] = {     0");
  240.     
  241.       j = 10;
  242.       for (i = 1; i <= max_user_token_number; i++)
  243.     {
  244.       putc(',', ftable);
  245.     
  246.       if (j >= 10)
  247.         {
  248.           putc('\n', ftable);
  249.           j = 1;
  250.         }
  251.       else
  252.         {
  253.           j++;
  254.         }
  255.     
  256.       fprintf(ftable, "%6d", token_translations[i]);
  257.     }
  258.     
  259.       fprintf(ftable, "\n};\n");
  260.     }
  261.   else
  262.     {
  263.       fprintf(ftable, "\n#define YYTRANSLATE(x) (x)\n");
  264.     } 
  265. }
  266.  
  267.  
  268.  
  269. output_gram()
  270. {
  271.   register int i;
  272.   register int j;
  273.   register short *sp;
  274.  
  275.   fprintf(ftable, "\nstatic short yyprhs[] = {     0");
  276.  
  277.   j = 10;
  278.   for (i = 1; i < nrules; i++)
  279.     {
  280.       putc(',', ftable);
  281.  
  282.       if (j >= 10)
  283.     {
  284.       putc('\n', ftable);
  285.       j = 1;
  286.     }
  287.       else
  288.     {
  289.       j++;
  290.     }
  291.  
  292.       fprintf(ftable, "%6d", rrhs[i]);
  293.     }
  294.  
  295.   fprintf(ftable, "\n};\n\nstatic short yyrhs[] = {%6d", ritem[0]);
  296.  
  297.   j = 10;
  298.   for (sp = ritem + 1; *sp; sp++)
  299.     {
  300.       putc(',', ftable);
  301.  
  302.       if (j >= 10)
  303.     {
  304.       putc('\n', ftable);
  305.       j = 1;
  306.     }
  307.       else
  308.     {
  309.       j++;
  310.     }
  311.  
  312.       if (*sp > 0)
  313.     fprintf(ftable, "%6d", *sp);
  314.       else
  315.     fprintf(ftable, "     0");
  316.     }
  317.  
  318.   fprintf(ftable, "\n};\n");
  319. }
  320.  
  321.  
  322.  
  323. output_stos()
  324. {
  325.   register int i;
  326.   register int j;
  327.  
  328.   fprintf(ftable, "\nstatic short yystos[] = {     0");
  329.  
  330.   j = 10;
  331.   for (i = 1; i < nstates; i++)
  332.     {
  333.       putc(',', ftable);
  334.  
  335.       if (j >= 10)
  336.     {
  337.       putc('\n', ftable);
  338.       j = 1;
  339.     }
  340.       else
  341.     {
  342.       j++;
  343.     }
  344.  
  345.       fprintf(ftable, "%6d", accessing_symbol[i]);
  346.     }
  347.  
  348.   fprintf(ftable, "\n};\n");
  349. }
  350.  
  351.  
  352.  
  353. output_rule_data()
  354. {
  355.   register int i;
  356.   register int j;
  357.  
  358.   fprintf(ftable, "\nstatic short yyr1[] = {     0");
  359.  
  360.   j = 10;
  361.   for (i = 1; i <= nrules; i++)
  362.     {
  363.       putc(',', ftable);
  364.  
  365.       if (j >= 10)
  366.     {
  367.       putc('\n', ftable);
  368.       j = 1;
  369.     }
  370.       else
  371.     {
  372.       j++;
  373.     }
  374.  
  375.       fprintf(ftable, "%6d", rlhs[i]);
  376.     }
  377.  
  378.   FREE(rlhs + 1);
  379.  
  380.   fprintf(ftable, "\n};\n\nstatic short yyr2[] = {     0");
  381.  
  382.   j = 10;
  383.   for (i = 1; i < nrules; i++)
  384.     {
  385.       putc(',', ftable);
  386.  
  387.       if (j >= 10)
  388.     {
  389.       putc('\n', ftable);
  390.       j = 1;
  391.     }
  392.       else
  393.     {
  394.       j++;
  395.     }
  396.  
  397.       fprintf(ftable, "%6d", rrhs[i + 1] - rrhs[i] - 1);
  398.     }
  399.  
  400.   putc(',', ftable);
  401.   if (j >= 10)
  402.     putc('\n', ftable);
  403.  
  404.   fprintf(ftable, "%6d\n};\n", nitems - rrhs[nrules] - 1);
  405.   FREE(rrhs + 1);
  406. }
  407.  
  408.  
  409.  
  410. output_defines()
  411. {
  412.   fprintf(ftable, "\n\n#define\tYYFINAL\t\t%d\n", final_state);
  413.   fprintf(ftable, "#define\tYYFLAG\t\t%d\n", MINSHORT);
  414.   fprintf(ftable, "#define\tYYNTBASE\t%d\n", ntokens);
  415. }
  416.  
  417.  
  418.  
  419. /* compute and output yydefact, yydefgoto, yypact, yypgoto, yytable and yycheck.  */
  420.  
  421. output_actions()
  422. {
  423.   nvectors = nstates + nvars;
  424.  
  425.   froms = NEW2(nvectors, short *);
  426.   tos = NEW2(nvectors, short *);
  427.   tally = NEW2(nvectors, short);
  428.   width = NEW2(nvectors, short);
  429.  
  430.   token_actions();
  431.   free_shifts();
  432.   free_reductions();
  433.   FREE(lookaheads);
  434.   FREE(LA);
  435.   FREE(LAruleno);
  436.   FREE(accessing_symbol);
  437.  
  438.   goto_actions();
  439.   FREE(goto_map);
  440.   FREE(from_state);
  441.   FREE(to_state);
  442.  
  443.   sort_actions();
  444.   pack_table();
  445.   output_base();
  446.   output_table();
  447.   output_check();
  448. }
  449.  
  450.  
  451.  
  452. /* figure out the actions for the specified state, indexed by lookahead token type.
  453.  
  454.    The yydefact table is output now.  The detailed info
  455.    is saved for putting into yytable later.  */
  456.  
  457. token_actions()
  458. {
  459.   register int i;
  460.   register int j;
  461.   register int k;
  462.  
  463.   actrow = NEW2(ntokens, short);
  464.  
  465.   k = action_row(0);
  466.   fprintf(ftable, "\nstatic short yydefact[] = {%6d", k);
  467.   save_row(0);
  468.  
  469.   j = 10;
  470.   for (i = 1; i < nstates; i++)
  471.     {
  472.       putc(',', ftable);
  473.  
  474.       if (j >= 10)
  475.     {
  476.       putc('\n', ftable);
  477.       j = 1;
  478.     }
  479.       else
  480.     {
  481.       j++;
  482.     }
  483.  
  484.       k = action_row(i);
  485.       fprintf(ftable, "%6d", k);
  486.       save_row(i);
  487.     }
  488.  
  489.   fprintf(ftable, "\n};\n");
  490.   FREE(actrow);
  491. }
  492.  
  493.  
  494.  
  495. /* Decide what to do for each type of token if seen as the lookahead token in specified state.
  496.    The value returned is used as the default action (yydefact) for the state.
  497.    In addition, actrow is filled with what to do for each kind of token,
  498.    index by symbol number, with zero meaning do the default action.
  499.  
  500.    This is where conflicts are resolved.  The loop over lookahead rules
  501.    considered lower-numbered rules last, and the last rule considered that likes
  502.    a token gets to handle it.  */
  503.  
  504. int
  505. action_row(state)
  506. int state;
  507. {
  508.   register int i;
  509.   register int j;
  510.   register int k;
  511.   register int m;
  512.   register int n;
  513.   register int count;
  514.   register int default_rule;
  515.   register int nreds;
  516.   register int maxcount;
  517.   register int rule;
  518.   register int shift_state;
  519.   register int symbol;
  520.   register unsigned mask;
  521.   register unsigned *wordp;
  522.   register reductions *redp;
  523.   register shifts *shiftp;
  524.   int nodefault = 0;  /* set nonzero to inhibit having any default reduction */
  525.  
  526.   for (i = 0; i < ntokens; i++)
  527.     actrow[i] = 0;
  528.  
  529.   default_rule = 0;
  530.   nreds = 0;
  531.   redp = reduction_table[state];
  532.  
  533.   if (redp)
  534.     {
  535.       nreds = redp->nreds;
  536.  
  537.       if (nreds >= 1)
  538.     {
  539.       /* loop over all the rules available here which require lookahead */
  540.       m = lookaheads[state];
  541.       n = lookaheads[state + 1];
  542.  
  543.       for (i = n - 1; i >= m; i--)
  544.         {
  545.           rule = - LAruleno[i];
  546.           wordp = LA + i * tokensetsize;
  547.           mask = 1;
  548.  
  549.           /* and find each token which the rule finds acceptable to come next */
  550.           for (j = 0; j < ntokens; j++)
  551.         {
  552.           /* and record this rule as the rule to use if that token follows.  */
  553.           if (mask & *wordp)
  554.             actrow[j] = rule;
  555.  
  556.           mask <<= 1;
  557.           if (mask == 0)
  558.             {
  559.               mask = 1;
  560.               wordp++;
  561.             }
  562.         }
  563.         }
  564.     }
  565.     }
  566.  
  567.   shiftp = shift_table[state];
  568.  
  569.   /* now see which tokens are allowed for shifts in this state.
  570.      For them, record the shift as the thing to do.  So shift is preferred to reduce.  */
  571.  
  572.   if (shiftp)
  573.     {
  574.       k = shiftp->nshifts;
  575.  
  576.       for (i = 0; i < k; i++)
  577.     {
  578.       shift_state = shiftp->shifts[i];
  579.       if (! shift_state) continue;
  580.  
  581.       symbol = accessing_symbol[shift_state];
  582.  
  583.       if (ISVAR(symbol))
  584.         break;
  585.  
  586.       actrow[symbol] = shift_state;
  587.  
  588.       /* do not use any default reduction if there is a shift for error */
  589.  
  590.       if (symbol == error_token_number) nodefault = 1;
  591.     }
  592.     }
  593.  
  594.   /* now find the most common reduction and make it the default action for this state.  */
  595.  
  596.   if (nreds >= 1 && ! nodefault)
  597.     {
  598.       if (consistent[state])
  599.     default_rule = redp->rules[0];
  600.       else
  601.     {
  602.       maxcount = 0;
  603.       for (i = m; i < n; i++)
  604.         {
  605.           count = 0;
  606.           rule = - LAruleno[i];
  607.     
  608.           for (j = 0; j < ntokens; j++)
  609.         {
  610.           if (actrow[j] == rule)
  611.             count++;
  612.         }
  613.     
  614.           if (count > maxcount)
  615.         {
  616.           maxcount = count;
  617.           default_rule = rule;
  618.         }
  619.         }
  620.     
  621.       /* actions which match the default are replaced with zero,
  622.          which means "use the default" */
  623.     
  624.       if (maxcount > 0)
  625.         {
  626.           for (j = 0; j < ntokens; j++)
  627.         {
  628.           if (actrow[j] == default_rule)
  629.             actrow[j] = 0;
  630.         }
  631.     
  632.           default_rule = - default_rule;
  633.         }
  634.     }
  635.     }
  636.  
  637.   return (default_rule);
  638. }
  639.  
  640.  
  641.  
  642. save_row(state)
  643. int state;
  644. {
  645.   register int i;
  646.   register int count;
  647.   register short *sp;
  648.   register short *sp1;
  649.   register short *sp2;
  650.  
  651.   count = 0;
  652.   for (i = 0; i < ntokens; i++)
  653.     {
  654.       if (actrow[i] != 0)
  655.     count++;
  656.     }
  657.  
  658.   if (count == 0)
  659.     return;
  660.  
  661.   froms[state] = sp1 = sp = NEW2(count, short);
  662.   tos[state] = sp2 = NEW2(count, short);
  663.  
  664.   for (i = 0; i < ntokens; i++)
  665.     {
  666.       if (actrow[i] != 0)
  667.     {
  668.       *sp1++ = i;
  669.       *sp2++ = actrow[i];
  670.     }
  671.     }
  672.  
  673.   tally[state] = count;
  674.   width[state] = sp1[-1] - sp[0] + 1;
  675. }
  676.  
  677.  
  678.  
  679. /* figure out what to do after reducing with each rule,
  680.    depending on the saved state from before the beginning
  681.    of parsing the data that matched this rule.
  682.  
  683.    The yydefgoto table is output now.  The detailed info
  684.    is saved for putting into yytable later.  */
  685.  
  686. goto_actions()
  687. {
  688.   register int i;
  689.   register int j;
  690.   register int k;
  691.  
  692.   state_count = NEW2(nstates, short);
  693.  
  694.   k = default_goto(ntokens);
  695.   fprintf(ftable, "\nstatic short yydefgoto[] = {%6d", k);
  696.   save_column(ntokens, k);
  697.  
  698.   j = 10;
  699.   for (i = ntokens + 1; i < nsyms; i++)
  700.     {
  701.       putc(',', ftable);
  702.  
  703.       if (j >= 10)
  704.     {
  705.       putc('\n', ftable);
  706.       j = 1;
  707.     }
  708.       else
  709.     {
  710.       j++;
  711.     }
  712.  
  713.       k = default_goto(i);
  714.       fprintf(ftable, "%6d", k);
  715.       save_column(i, k);
  716.     }
  717.  
  718.   fprintf(ftable, "\n};\n");
  719.   FREE(state_count);
  720. }
  721.  
  722.  
  723.  
  724. int
  725. default_goto(symbol)
  726. int symbol;
  727. {
  728.   register int i;
  729.   register int m;
  730.   register int n;
  731.   register int default_state;
  732.   register int maxcount;
  733.  
  734.   m = goto_map[symbol];
  735.   n = goto_map[symbol + 1];
  736.  
  737.   if (m == n)
  738.     return (-1);
  739.  
  740.   for (i = 0; i < nstates; i++)
  741.     state_count[i] = 0;
  742.  
  743.   for (i = m; i < n; i++)
  744.     state_count[to_state[i]]++;
  745.  
  746.   maxcount = 0;
  747.   default_state = -1;
  748.  
  749.   for (i = 0; i < nstates; i++)
  750.     {
  751.       if (state_count[i] > maxcount)
  752.     {
  753.       maxcount = state_count[i];
  754.       default_state = i;
  755.     }
  756.     }
  757.  
  758.   return (default_state);
  759. }
  760.  
  761.  
  762.  
  763. save_column(symbol, default_state)
  764. int symbol;
  765. int default_state;
  766. {
  767.   register int i;
  768.   register int m;
  769.   register int n;
  770.   register short *sp;
  771.   register short *sp1;
  772.   register short *sp2;
  773.   register int count;
  774.   register int symno;
  775.  
  776.   m = goto_map[symbol];
  777.   n = goto_map[symbol + 1];
  778.  
  779.   count = 0;
  780.   for (i = m; i < n; i++)
  781.     {
  782.       if (to_state[i] != default_state)
  783.     count++;
  784.     }
  785.  
  786.   if (count == 0)
  787.     return;
  788.  
  789.   symno = symbol - ntokens + nstates;
  790.  
  791.   froms[symno] = sp1 = sp = NEW2(count, short);
  792.   tos[symno] = sp2 = NEW2(count, short);
  793.  
  794.   for (i = m; i < n; i++)
  795.     {
  796.       if (to_state[i] != default_state)
  797.     {
  798.       *sp1++ = from_state[i];
  799.       *sp2++ = to_state[i];
  800.     }
  801.     }
  802.  
  803.   tally[symno] = count;
  804.   width[symno] = sp1[-1] - sp[0] + 1;
  805. }
  806.  
  807.  
  808.  
  809. /* the next few functions decide how to pack 
  810.    the actions and gotos information into yytable. */
  811.  
  812. sort_actions()
  813. {
  814.   register int i;
  815.   register int j;
  816.   register int k;
  817.   register int t;
  818.   register int w;
  819.  
  820.   order = NEW2(nvectors, short);
  821.   nentries = 0;
  822.  
  823.   for (i = 0; i < nvectors; i++)
  824.     {
  825.       if (tally[i] > 0)
  826.     {
  827.       t = tally[i];
  828.       w = width[i];
  829.       j = nentries - 1;
  830.  
  831.       while (j >= 0 && (width[order[j]] < w))
  832.         j--;
  833.  
  834.       while (j >= 0 && (width[order[j]] == w) && (tally[order[j]] < t))
  835.         j--;
  836.  
  837.       for (k = nentries - 1; k > j; k--)
  838.         order[k + 1] = order[k];
  839.  
  840.       order[j + 1] = i;
  841.       nentries++;
  842.     }
  843.     }
  844. }
  845.  
  846.  
  847.  
  848. pack_table()
  849. {
  850.   register int i;
  851.   register int place;
  852.   register int state;
  853.  
  854.   base = NEW2(nvectors, short);
  855.   pos = NEW2(nentries, short);
  856.   table = NEW2(MAXTABLE, short);
  857.   check = NEW2(MAXTABLE, short);
  858.  
  859.   lowzero = 0;
  860.   high = 0;
  861.  
  862.   for (i = 0; i < nvectors; i++)
  863.     base[i] = MINSHORT;
  864.  
  865.   for (i = 0; i < MAXTABLE; i++)
  866.     check[i] = -1;
  867.  
  868.   for (i = 0; i < nentries; i++)
  869.     {
  870.       state = matching_state(i);
  871.  
  872.       if (state < 0)
  873.     place = pack_vector(i);
  874.       else
  875.     place = base[state];
  876.  
  877.       pos[i] = place;
  878.       base[order[i]] = place;
  879.     }
  880.  
  881.   for (i = 0; i < nvectors; i++)
  882.     {
  883.       FREE(froms[i]);
  884.       FREE(tos[i]);
  885.     }
  886.  
  887.   FREE(froms);
  888.   FREE(tos);
  889.   FREE(pos);
  890. }
  891.  
  892.  
  893.  
  894. int
  895. matching_state(vector)
  896. int vector;
  897. {
  898.   register int i;
  899.   register int j;
  900.   register int k;
  901.   register int t;
  902.   register int w;
  903.   register int match;
  904.   register int prev;
  905.  
  906.   i = order[vector];
  907.   if (i >= nstates)
  908.     return (-1);
  909.  
  910.   t = tally[i];
  911.   w = width[i];
  912.  
  913.   for (prev = vector - 1; prev >= 0; prev--)
  914.     {
  915.       j = order[prev];
  916.       if (width[j] != w || tally[j] != t)
  917.     return (-1);
  918.  
  919.       match = 1;
  920.       for (k = 0; match && k < t; k++)
  921.     {
  922.       if (tos[j][k] != tos[i][k] || froms[j][k] != froms[i][k])
  923.         match = 0;
  924.     }
  925.  
  926.       if (match)
  927.     return (j);
  928.     }
  929.  
  930.   return (-1);
  931. }
  932.  
  933.  
  934.  
  935. int
  936. pack_vector(vector)
  937. int vector;
  938. {
  939.   register int i;
  940.   register int j;
  941.   register int k;
  942.   register int t;
  943.   register int loc;
  944.   register int ok;
  945.   register short *from;
  946.   register short *to;
  947.  
  948.   i = order[vector];
  949.   t = tally[i];
  950.  
  951.   if (t == 0)
  952.     berror("pack_vector");
  953.  
  954.   from = froms[i];
  955.   to = tos[i];
  956.  
  957.   for (j = lowzero - from[0]; j < MAXTABLE; j++)
  958.     {
  959.       ok = 1;
  960.  
  961.       for (k = 0; ok && k < t; k++)
  962.     {
  963.       loc = j + from[k];
  964.       if (loc > MAXTABLE)
  965.         fatal("maximum table size exceeded");
  966.  
  967.       if (table[loc] != 0)
  968.         ok = 0;
  969.     }
  970.  
  971.       for (k = 0; ok && k < vector; k++)
  972.     {
  973.       if (pos[k] == j)
  974.         ok = 0;
  975.     }
  976.  
  977.       if (ok)
  978.     {
  979.       for (k = 0; k < t; k++)
  980.         {
  981.           loc = j + from[k];
  982.           table[loc] = to[k];
  983.           check[loc] = from[k];
  984.         }
  985.  
  986.       while (table[lowzero] != 0)
  987.         lowzero++;
  988.  
  989.       if (loc > high)
  990.         high = loc;
  991.  
  992.       return (j);
  993.     }
  994.     }
  995.  
  996.   berror("pack_vector");
  997. }
  998.  
  999.  
  1000.  
  1001. /* the following functions output yytable, yycheck
  1002.    and the vectors whose elements index the portion starts */
  1003.  
  1004. output_base()
  1005. {
  1006.   register int i;
  1007.   register int j;
  1008.  
  1009.   fprintf(ftable, "\nstatic short yypact[] = {%6d", base[0]);
  1010.  
  1011.   j = 10;
  1012.   for (i = 1; i < nstates; i++)
  1013.     {
  1014.       putc(',', ftable);
  1015.  
  1016.       if (j >= 10)
  1017.     {
  1018.       putc('\n', ftable);
  1019.       j = 1;
  1020.     }
  1021.       else
  1022.     {
  1023.       j++;
  1024.     }
  1025.  
  1026.       fprintf(ftable, "%6d", base[i]);
  1027.     }
  1028.  
  1029.   fprintf(ftable, "\n};\n\nstatic short yypgoto[] = {%6d", base[nstates]);
  1030.  
  1031.   j = 10;
  1032.   for (i = nstates + 1; i < nvectors; i++)
  1033.     {
  1034.       putc(',', ftable);
  1035.  
  1036.       if (j >= 10)
  1037.     {
  1038.       putc('\n', ftable);
  1039.       j = 1;
  1040.     }
  1041.       else
  1042.     {
  1043.       j++;
  1044.     }
  1045.  
  1046.       fprintf(ftable, "%6d", base[i]);
  1047.     }
  1048.  
  1049.   fprintf(ftable, "\n};\n");
  1050.   FREE(base);
  1051. }
  1052.  
  1053.  
  1054.  
  1055. output_table()
  1056. {
  1057.   register int i;
  1058.   register int j;
  1059.  
  1060.   fprintf(ftable, "\n\n#define\tYYLAST\t\t%d\n\n", high);
  1061.   fprintf(ftable, "\nstatic short yytable[] = {%6d", table[0]);
  1062.  
  1063.   j = 10;
  1064.   for (i = 1; i <= high; i++)
  1065.     {
  1066.       putc(',', ftable);
  1067.  
  1068.       if (j >= 10)
  1069.     {
  1070.       putc('\n', ftable);
  1071.       j = 1;
  1072.     }
  1073.       else
  1074.     {
  1075.       j++;
  1076.     }
  1077.  
  1078.       fprintf(ftable, "%6d", table[i]);
  1079.     }
  1080.  
  1081.   fprintf(ftable, "\n};\n");
  1082.   FREE(table);
  1083. }
  1084.  
  1085.  
  1086.  
  1087. output_check()
  1088. {
  1089.   register int i;
  1090.   register int j;
  1091.  
  1092.   fprintf(ftable, "\nstatic short yycheck[] = {%6d", check[0]);
  1093.  
  1094.   j = 10;
  1095.   for (i = 1; i <= high; i++)
  1096.     {
  1097.       putc(',', ftable);
  1098.  
  1099.       if (j >= 10)
  1100.     {
  1101.       putc('\n', ftable);
  1102.       j = 1;
  1103.     }
  1104.       else
  1105.     {
  1106.       j++;
  1107.     }
  1108.  
  1109.       fprintf(ftable, "%6d", check[i]);
  1110.     }
  1111.  
  1112.   fprintf(ftable, "\n};\n");
  1113.   FREE(check);
  1114. }
  1115.  
  1116.  
  1117.  
  1118. /* copy the parser code into the ftable file at the end.  */
  1119.  
  1120. output_parser()
  1121. {
  1122.   register int c;
  1123.   FILE *fpars;
  1124.  
  1125.   if (pure_parser)
  1126.     fprintf(ftable, "#define YYIMPURE 1\n\n");
  1127.   else
  1128.     fprintf(ftable, "#define YYPURE 1\n\n");
  1129.  
  1130.   if (semantic_parser)
  1131.     fpars = fparser;
  1132.   else fpars = fparser1;
  1133.  
  1134.   c = getc(fpars);
  1135.   while (c != EOF)
  1136.     {
  1137.       if (c == '$')
  1138.         fprintf(ftable, "#include \"%s\"\n", actfile);
  1139.       else
  1140.     putc(c, ftable);
  1141.       c = getc(fpars);
  1142.     }
  1143. }
  1144.  
  1145.  
  1146.  
  1147. output_program()
  1148. {
  1149.   register int c;
  1150.   extern int lineno;
  1151.  
  1152.   fprintf(ftable, "#line %d \"%s\"\n", lineno, infile);
  1153.  
  1154.   c = getc(finput);
  1155.   while (c != EOF)
  1156.     {
  1157.       putc(c, ftable);
  1158.       c = getc(finput);
  1159.     }
  1160. }
  1161.  
  1162.  
  1163.  
  1164. free_itemsets()
  1165. {
  1166.   register core *cp;
  1167.  
  1168.   FREE(state_table);
  1169.  
  1170.   for (cp = first_state; cp; cp = cp->next)
  1171.     FREE(cp);
  1172. }
  1173.  
  1174.  
  1175.  
  1176. free_shifts()
  1177. {
  1178.   register shifts *sp;
  1179.  
  1180.   FREE(shift_table);
  1181.  
  1182.   for (sp = first_shift; sp; sp = sp->next)
  1183.     FREE(sp);
  1184. }
  1185.  
  1186.  
  1187.  
  1188. free_reductions()
  1189. {
  1190.   register reductions *rp;
  1191.  
  1192.   FREE(reduction_table);
  1193.  
  1194.   for (rp = first_reduction; rp; rp = rp->next)
  1195.     FREE(rp);
  1196. }
  1197.  
  1198. emit (stp)
  1199. char **stp;
  1200. {
  1201.     while (stp && *stp) {
  1202.     fprintf (faction, "%s", *stp++);
  1203.     }
  1204. }
  1205.